#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stack>
using namespace std;
typedef struct bst_tree
{
    int data;
    struct bst_tree *lchild,*rchild;
}treeNode;

treeNode *newNode(int val){
    treeNode *node=(treeNode *) malloc(sizeof(treeNode)*1);
    node->data=val;
    node->lchild=nullptr;
    node->rchild=nullptr;
    return node;
}
treeNode *create_bst(treeNode* node,int data){
    if(!node)
        return newNode(data);
    if(node->data>data)
        node->lchild=create_bst(node->lchild,data);
    else
        node->rchild=create_bst(node->rchild,data);
    return node;//返回 插入了节点的 根节点
}
void preOrder_Iterative(treeNode *root){
    if(NULL==root)
        return;
    stack<treeNode *> nodeStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        treeNode *node=nodeStack.top();
        printf("%d ",node->data);
        nodeStack.pop();
        if(node->rchild) nodeStack.push(node->rchild);
        if(node->lchild) nodeStack.push(node->lchild);
    }
}
treeNode *minValNode(treeNode *root){
    if(NULL==root)
        return root;
    treeNode *curNode=root;
    while(curNode->lchild){
        //往左找
        curNode=curNode->lchild;
    }
    return curNode;
}
/*
*删除某个节点：
*1.叶子节点直接删
*2.要删除的节点只有一个子节点 子节点替，然后删除子节点
*3.要删除的节点有两个子节点 往左找最大或者往右找最小的(中序遍历中待删除节点x的后继y)，按2的方法操作
*@返回值 treeNode* 是deleteNode后新树的根节点
*@param root 是每次递归时的节点（初始为原bst树的根节点）
*@param key 是待删除节点的值
*/
treeNode *deleteNode(treeNode *root,int key){
    if(NULL==root)
        return root;
    if(key<root->data)
        root->lchild=deleteNode(root->lchild,key);
    else if(key>root->data)
        root->rchild=deleteNode(root->rchild,key);
    else{
        if(root->lchild==NULL){//只有一个叶子节点或者无节点
            treeNode *temp=root->rchild;
            free(root);
            return temp;//这里因为递归首先出去的 是root的右子树，所以取右孩子先考虑
        }
        if(root->rchild==NULL){
            treeNode *temp=root->lchild;
            free(root);
            return temp;
        }
        //两个子节点：找右子树最小元素
        treeNode *temp=minValNode(root->rchild);
        root->data=temp->data;//把待删除节点的值赋值为右子树最小元素的值
        root->rchild=deleteNode(root->rchild,temp->data);//转化成1，2类型去删除
    }
    return root;
}
int main(){
    treeNode *root=NULL;
    //srand(time(0));
    // rand()%(n-m+1)+m
    for(int i=0;i<5;i++){
        root=create_bst(root,i);
    }
    preOrder_Iterative(root);
    root=deleteNode(root,0);
    putchar('\n');
    preOrder_Iterative(root);
    return 0;
}